knapsack problem

application, mathematics Given a set of items, each with a

cost and a value, determine the number of each item to include

in a collection so that the total cost is less than some given

cost and the total value is as large as possible.

The 0/1 knapsack problem restricts the number of each items to

zero or one.

Such constraint satisfaction problems are often solved using

dynamic programming.

The general knapsack problem is NP-hard, and this has led to

attempts to use it as the basis for public-key encryption

systems. Several such attempts failed because the knapsack

problems they produced were in fact solvable by

polynomial-time algorithms.

[Are there any trusted knapsack-based public-key

cryptosystems?].

(1995-04-10)